/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/decode-string
   @Language: C++
   @Datetime: 19-05-09 14:47
   */

class Solution {
public:
	/**
	 * @param nums: a list of integers
	 * @return: return a integer
	 */
	int findShortestSubArray(vector<int> &nums) {
		// write your code here
		unordered_map<int,pair<int,int> > ranges;   // num, range
		unordered_map<int,int> freqs;    // num, freq
		for(int i=0; i<nums.size(); ++i){
			freqs[nums[i]]++;
			if(ranges.count(nums[i])<1) ranges[nums[i]]=make_pair(i,i);
			else ranges[nums[i]]=make_pair(ranges[nums[i]].first,i);
		}
		multimap<int,int> degrees;   // freq, num
		for(const auto &p:freqs)
			degrees.insert(make_pair(p.second,p.first));
		int freq=degrees.rbegin()->first, range=INT_MAX;
		for(auto it=degrees.rbegin(); it!=degrees.rend(); ++it){
			if(it->first<freq) break;
			range=min(range,1+ranges[it->second].second-ranges[it->second].first);
		}
		return range;
	}
};
